package com.leetcode.algorithm.y22.m07.w4;

/**
 * 240. 搜索二维矩阵 II
 * 
 * https://leetcode.cn/problems/search-a-2d-matrix-ii/
 * 
 * @author jie.deng
 *
 */
class Question0240Solution01 {

	public boolean searchMatrix(int[][] matrix, int target) {
		int rows = matrix.length;
		int cols = matrix[0].length;
		return search(matrix, 0, rows - 1, 0, cols - 1, target);
	}

	private boolean search(int[][] matrix, int leftRow, int rightRow, int leftCol, int rightCol, int target) {
		if (leftRow > rightRow) {
			return false;
		}
		if (leftCol == rightCol) {
			return searchCol(matrix, leftRow, rightRow, leftCol, target);
		}
		int col = searchRow(matrix[leftRow], leftCol, rightCol, target);
		if (matrix[leftRow][col] == target) {
			return true;
		}
		return search(matrix, leftRow + 1, rightRow, leftCol, col, target);
	}

	private boolean searchCol(int[][] matrix, int left, int right, int col, int target) {
		while (left <= right) {
			int mid = left + ((right - left) >> 1);
			if (matrix[mid][col] == target) {
				return true;
			} else if (matrix[mid][col] > target) {
				right = mid - 1;
			} else {
				left = mid + 1;
			}
		}
		return false;
	}

	/**
	 * 找第一个不小于target的元素的索引
	 * 
	 * @param arr
	 * @param target
	 * @return
	 */
	private int searchRow(int[] arr, int left, int right, int target) {
		while (left < right) {
			int mid = left + ((right - left) >> 1);
			if (arr[mid] == target) {
				return mid;
			} else if (arr[mid] > target) {
				right = mid;
			} else {
				left = mid + 1;
			}
		}
		return right;
	}

}